Monte-Carlo Tree Search

Monte-Carlo Tree Search (w skrócie MCTS) – heurystyka podejmowania decyzji w pewnych zadaniach sztucznej inteligencji, używana zwłaszcza do wyboru ruchów w grach. Sztandarowy przykład jej zastosowania to współczesne programy komputerowe do gry w go^[1]. Metodę MCTS stosuje się również w programach grających w inne gry planszowe (między innymi Hex^[2], Havannah^[3], Amazonki^[4] i Arimaa^[5]), w gry czasu rzeczywistego (na przykład Ms. Pac-Man^[6]) oraz w gry niedeterministyczne (na przykład skata^[7], pokera^[8], Magic: The Gathering^[9] czy Osadników z Catanu^[10]). Metoda MCTS skupia się na analizie najbardziej obiecujących ruchów, opierając rozrost drzewa wariantów na losowym próbkowaniu przestrzeni przeszukiwań.

↑ MCTS.ai: Everything Monte Carlo Tree Search. [dostęp 2012-02-19].
↑ Broderick Arneson, Ryan Hayward, Philip Henderson. MoHex Wins Hex Tournament. „ICGA Journal”. 32 (2), s. 114–116, czerwiec 2009.
↑ Timo Ewalds: Playing and Solving Havannah. Praca magisterska, University of Alberta, 2011.
↑ Richard J. Lorentz: Amazons Discover Monte-Carlo. W: Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H.M. Winands (red.). Springer, 2008, s. 13–24. ISBN 978-3-540-87607-6.
↑ Tomáš Kozelek: Methods of MCTS and the game Arimaa. Praca magisterska, Uniwersytet Karola w Pradze, 2009.
↑ Xiaocong Gan, Yun Bao, Zhangang Han. Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man. „ICGA Journal”. 34 (4), s. 209–222, grudzień 2011.
↑ Michael Buro, Jeffrey Richard Long, Timothy Furtak, Nathan R. Sturtevant: Improving State Evaluation, Inference, and Search in Trick-Based Card Games. W: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009. Craig Boutilier (red.). 2009, s. 1407–1413.
↑ Jonathan Rubin, Ian Watson. Computer poker: A review. „Artificial Intelligence”. 175 (5–6), kwiecień 2011. DOI: 10.1016/j.artint.2010.12.005.
↑ C.D. Ward, P.I. Cowling: Monte Carlo Search Applied to Card Selection in Magic: The Gathering. W: CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games. IEEE Press, 2009.
↑ István Szita, Guillaume Chaslot, Pieter Spronck: Monte-Carlo Tree Search in Settlers of Catan. W: Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers. H. Jaap van den Herik, Pieter Spronck (red.). Springer, 2010, s. 21–32. ISBN 978-3-642-12992-6.

[1] MCTS.ai: Everything Monte Carlo Tree Search. [dostęp 2012-02-19].

[2] Broderick Arneson, Ryan Hayward, Philip Henderson. MoHex Wins Hex Tournament. „ICGA Journal”. 32 (2), s. 114–116, czerwiec 2009.

[3] Timo Ewalds: Playing and Solving Havannah. Praca magisterska, University of Alberta, 2011.

[4] Richard J. Lorentz: Amazons Discover Monte-Carlo. W: Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H.M. Winands (red.). Springer, 2008, s. 13–24. ISBN 978-3-540-87607-6.

[5] Tomáš Kozelek: Methods of MCTS and the game Arimaa. Praca magisterska, Uniwersytet Karola w Pradze, 2009.

[6] Xiaocong Gan, Yun Bao, Zhangang Han. Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man. „ICGA Journal”. 34 (4), s. 209–222, grudzień 2011.

[7] Michael Buro, Jeffrey Richard Long, Timothy Furtak, Nathan R. Sturtevant: Improving State Evaluation, Inference, and Search in Trick-Based Card Games. W: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009. Craig Boutilier (red.). 2009, s. 1407–1413.

[8] Jonathan Rubin, Ian Watson. Computer poker: A review. „Artificial Intelligence”. 175 (5–6), kwiecień 2011. DOI: 10.1016/j.artint.2010.12.005.

[9] C.D. Ward, P.I. Cowling: Monte Carlo Search Applied to Card Selection in Magic: The Gathering. W: CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games. IEEE Press, 2009.

[10] István Szita, Guillaume Chaslot, Pieter Spronck: Monte-Carlo Tree Search in Settlers of Catan. W: Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers. H. Jaap van den Herik, Pieter Spronck (red.). Springer, 2010, s. 21–32. ISBN 978-3-642-12992-6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]